package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;

/**
 * @author GaoFeng2017
 * @date 2020/7/25 14:53
 */

public class BottomUpMergeSortV2 implements Sort {

    private static final int BASE_NUMBER = 2;

    /** 进行归并的数组的最小长度 */
    private static final int MERGE_MIN_LENGTH = 7;

    /** 辅助数组 */
    private Comparable[] auxiliaryElements;

    @Override
    public void sort(Comparable[] elements) {

        this.auxiliaryElements = new Comparable[elements.length];

        // 1,2,4,8
        for (int partition = 1; partition < elements.length; partition *= BASE_NUMBER) {
            // System.out.println("partition: " + partition);
            // elements.length - partition? merge condition: 10-[4,4,2], 2 is already merge,but 11-4,4,3, [8,9] need merge with [10]
            for (int beginIndex = 0; beginIndex < elements.length - partition; beginIndex += partition * BASE_NUMBER) {

                // 1, 2, 4,
                int estimateEndIndex = beginIndex + partition + partition - 1;
                int realEndIndex = Math.min(estimateEndIndex, elements.length - 1);

                if (partition <= MERGE_MIN_LENGTH) {
                    this.insertionSort(elements, beginIndex, realEndIndex);
                } else {
                    int mid = beginIndex + partition - 1;
                    // 两个数组已经有序，直接跳过。
                    if (SortUtil.less(elements[mid], elements[mid + 1])) {
                        continue;
                    }
                    this.merge(elements, beginIndex, mid, realEndIndex);
                }

            }

        }
    }

    private void merge(Comparable[] elements, int beginIndex, int mid, int endIndex) {

        // System.out.println(beginIndex + ", " + mid + ", " + endIndex);

        for (int i = beginIndex; i <= mid; i++) {
            this.auxiliaryElements[i] = elements[i];
        }

        for (int i = mid + 1; i <= endIndex; i++) {
            this.auxiliaryElements[i] = elements[mid + (endIndex - i) + 1];
        }

        int leftIndex = beginIndex;
        int rightIndex = endIndex;
        for (int i = beginIndex; i <= endIndex; i++) {
            if (SortUtil.less(this.auxiliaryElements[rightIndex], this.auxiliaryElements[leftIndex])) {
                elements[i] = this.auxiliaryElements[rightIndex--];
            } else {
                elements[i] = this.auxiliaryElements[leftIndex++];
            }
        }
    }

    // 插入排序。
    private void insertionSort(Comparable[] elements, int beginIndex, int endIndex) {
        for (int i = beginIndex + 1; i <= endIndex; i++) {
            for (int j = i; j > beginIndex && SortUtil.less(elements[j], elements[j - 1]); j--) {
                // 插入排序，交换两个元素的位置
                SortUtil.exchange(elements, j, j - 1);
            }
        }
    }


}
